package SingleLinkedList;

import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;

import static SingleLinkedList.SmallerEqualBigger.*;

public class ReverseNodesInkGroup {

    public static void main(String[] args) {
        generateSingleLinkListByString("1->2->3->4")
                .ifPresent(head -> reverseKGroup(head, 5).print());
    }

    public static Optional<Node> generateSingleLinkListByString(String string) {
        if (string.isEmpty()) {
            return Optional.empty();
        }
        List<Node> collect = Arrays.stream(string.split("->"))
                .mapToInt(Integer::parseInt)
                .mapToObj(Node::new)
                .collect(Collectors.toList());
        Iterator<Node> iterator = collect.iterator();
        Node head = iterator.next();
        Node cur = head;
        while (iterator.hasNext()) {
            cur.next = iterator.next();
            cur = cur.next;
        }
        return Optional.of(head);
    }

    public static Node reverseKGroup(Node head, int k) {
        Node start = head;
        Optional<Node> end = teamEnd(start, k);

        if (!end.isPresent()) {
            // 链表里面的数据量，连一组都划分不出来
            // eg: 1 -> 2, k = 3
            return head;
        }

        // 第一组很特殊，因为牵扯到换头的问题
        head = end.orElse(null);
        reverse(start, end.orElse(null));

        // 翻转之后start变成了上一组的结尾节点
        Node lastTeamEnd = start;


        while (lastTeamEnd.next != null) {
            start = lastTeamEnd.next;
            end = teamEnd(start, k);

            if (!end.isPresent()) {
                // 第一组够分，后面不够分
                // example: 1 -> 2 -> 3, k = 2
                return head;
            }

            reverse(start, end.orElse(null));
            // 上一组的尾巴连接下一组的end
            lastTeamEnd.next = end.orElse(null);
            lastTeamEnd = start;
        }

        return head;
    }

    /**
     * example: a -> b -> c -> d
     * 处理后: d -> c -> b -> a
     *
     * @param start 链表开始节点
     * @param end   链表结束节点
     */
    private static void reverse(Node start, Node end) {
        end = end.next;
        Node pre = null, cur = start;

        while (cur != end) {
            // 指向前一个
            cur.next = pre;
            // 当前的变前一个
            pre = cur;
            // 下一个变当前一个
            cur = cur.next;
        }

        // 反转之后，开始节点变成结尾节点，指向后面的节点
        start.next = end;
    }

    private static Optional<Node> teamEnd(Node start, int k) {
        while (--k != 0 && start != null) {
            start = start.next;
        }

        return Optional.ofNullable(start);
    }
}
